import java.util.Stack;

/**
 * @program: LeetCode
 * @description: LeetCode :
 * @author: WXY
 * @create: 2022-12-30 12:04
 * @Version 1.0
 **/


public class offer_thirteen1_largestRectangleArea {
    public static int largestRectangleArea(int[] heights) {
        int[] arr = new int[heights.length + 1];
        int index = 0;
        for (int i : heights) {
            arr[index++] = i;
        }
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        int maxArea = 0;
        for (int i = 0; i < arr.length; i++) {
            while (stack.peek() != -1 && arr[stack.peek()] > arr[i]) {
                int height = arr[stack.pop()];
                int width = i - stack.peek() - 1;
                maxArea = Math.max(maxArea, height * width);
            }
            stack.push(i);
        }
        return maxArea;
    }
}
